Micron Document
`:top
The `!bitap algorithm`! (also known as the `!shift-or`!, `!shift-and`! or `!Baeza-Yates–Gonnet`! algorithm) is an `F33f`_`[approximate string matching`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Approximate_string_matching]`_`f algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of `F33f`_`[Levenshtein distance`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Levenshtein_distance]`_`f – if the substring and pattern are within a given distance `*k`* of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of `F33f`_`[bitmasks`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitmask]`_`f containing one bit for each element of the pattern. Then it is able to do most of the work with `F33f`_`[bitwise operations`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitwise_operation]`_`f, which are extremely fast.

The bitap algorithm is perhaps best known as one of the underlying algorithms of the `F33f`_`[Unix`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Unix]`_`f `F33f`_`[utility`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Programming_tool]`_`f `F33f`_`[agrep`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Agrep]`_`f, written by `F33f`_`[Udi Manber`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Udi_Manber]`_`f, Sun Wu, and Burra Gopal. Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general `F33f`_`[regular expressions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Regular_expression]`_`f.

Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the `F33f`_`[word length`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Word_length]`_`f of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length `*m`*, however, its `F33f`_`[running time`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Running_time]`_`f is completely predictable – it runs in `F33f`_`[O`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Big_O_notation]`_`f(`*mn`*) operations, no matter the structure of the text or the pattern.

The bitap algorithm for exact string searching was invented by Bálint Dömölki in 1964`:ref-domolki64`a[1]`:ref-domolki68`a[2] and extended by R. K. Shyamasundar in 1977`:ref-shyamasundar77`a[3], before being reinvented by `F33f`_`[Ricardo Baeza-Yates`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Ricardo_Baeza-Yates]`_`f and `F33f`_`[Gaston Gonnet`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Gaston_Gonnet]`_`f`:ref-byg92`a[4] in 1989 (one chapter of first author's PhD thesis`:ref-by89`a[5]) which also extended it to handle classes of characters, wildcards, and mismatches. In 1991, it was extended by `F33f`_`[Manber`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Udi_Manber]`_`f and Wu `:ref-manber91`a[6]`:ref-manber92`a[7] to handle also insertions and deletions (full fuzzy string searching). This algorithm was later improved by Baeza-Yates and `F33f`_`[Navarro`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Gonzalo_Navarro]`_`f in 1996.`:ref-bn96`a[8]

>>Contents

• `F0af`_`[Exact searching`#exact-searching]`_`f
• `F0af`_`[Fuzzy searching`#fuzzy-searching]`_`f
• `F0af`_`[See also`#see-also]`_`f
• `F0af`_`[External links and references`#external-links-and-references]`_`f

-─

>>Exact searching

The bitap algorithm for exact `F33f`_`[string searching`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=String_searching_algorithm]`_`f, in full generality, looks like this in pseudocode:

`B100`F9d9algorithm bitap_search is`f`b
`B100`F9d9 input: text as a string.`f`b
`B100`F9d9 pattern as a string.`f`b
`B100`F9d9 output: string`f`b
`B100`F9d9 m := length(pattern)`f`b
`B100`F9d9`f`b
`B100`F9d9 if m = 0 then`f`b
`B100`F9d9 return text`f`b
`B100`F9d9`f`b
`B100`F9d9 /* Initialize the bit array R. */`f`b
`B100`F9d9 R := new array[m+1] of bit, initially all 0`f`b
`B100`F9d9 R[0] := 1`f`b
`B100`F9d9`f`b
`B100`F9d9 for i := 0; i < length(text); i += 1 do`f`b
`B100`F9d9 /* Update the bit array. */`f`b
`B100`F9d9 for k := m; k ≥ 1; k -= 1 do`f`b
`B100`F9d9 R[k] := R[k - 1] & (text[i] = pattern[k - 1])`f`b
`B100`F9d9`f`b
`B100`F9d9 if R[m] then`f`b
`B100`F9d9 return (text + i - m) + 1`f`b
`B100`F9d9`f`b
`B100`F9d9 return null`f`b

Bitap distinguishes itself from other well-known string searching algorithms in its natural mapping onto simple bitwise operations, as in the following modification of the above program. Notice that in this implementation, counterintuitively, each bit with value zero indicates a match, and each bit with value 1 indicates a non-match. The same algorithm can be written with the intuitive semantics for 0 and 1, but in that case we must introduce another instruction into the `F33f`_`[inner loop`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Inner_loop]`_`f to set `B100`F9d9R |= 1`f`b. In this implementation, we take advantage of the fact that left-shifting a value shifts in zeros on the right, which is precisely the behavior we need.

Notice also that we require `B100`F9d9CHAR_MAX`f`b additional bitmasks in order to convert the `B100`F9d9(text[i] == pattern[k-1])`f`b condition in the general implementation into bitwise operations. Therefore, the bitap algorithm performs better when applied to inputs over smaller alphabets.

`B100`F9d9 #include <string.h>`f`b
`B100`F9d9 #include <limits.h>`f`b
`B100`F9d9`f`b
`B100`F9d9 const char *bitap_bitwise_search(const char *text, const char *pattern)`f`b
`B100`F9d9 {`f`b
`B100`F9d9 int m = strlen(pattern);`f`b
`B100`F9d9 unsigned long R;`f`b
`B100`F9d9 unsigned long pattern_mask[CHAR_MAX+1];`f`b
`B100`F9d9 int i;`f`b
`B100`F9d9`f`b
`B100`F9d9 if (m == 0) return text;`f`b
`B100`F9d9 if (m > 31) throw "The pattern is too long!";`f`b
`B100`F9d9`f`b
`B100`F9d9 /* Initialize the bit array R */`f`b
`B100`F9d9 R = ~1;`f`b
`B100`F9d9`f`b
`B100`F9d9 /* Initialize the pattern bitmasks */`f`b
`B100`F9d9 for (i=0; i <= CHAR_MAX; ++i)`f`b
`B100`F9d9 pattern_mask[i] = ~0;`f`b
`B100`F9d9 for (i=0; i < m; ++i)`f`b
`B100`F9d9 pattern_mask[pattern[i]] &= ~(1UL << i);`f`b
`B100`F9d9`f`b
`B100`F9d9 for (i=0; text[i] != '\\0'; ++i) {`f`b
`B100`F9d9 /* Update the bit array */`f`b
`B100`F9d9 R |= pattern_mask[text[i]];`f`b
`B100`F9d9 R <<= 1;`f`b
`B100`F9d9`f`b
`B100`F9d9 if (0 == (R & (1UL << m)))`f`b
`B100`F9d9 return (text + i - m) + 1;`f`b
`B100`F9d9 }`f`b
`B100`F9d9`f`b
`B100`F9d9 return NULL;`f`b
`B100`F9d9 }`f`b

>>Fuzzy searching

To perform fuzzy string searching using the bitap algorithm, it is necessary to extend the bit array `*R`* into a second dimension. Instead of having a single array `*R`* that changes over the length of the text, we now have `*k`* distinct arrays `*R`*1..`*k`*. Array `*Ri`* holds a representation of the prefixes of `*pattern`* that match any suffix of the current string with `*i`* or fewer errors. In this context, an "error" may be an insertion, deletion, or substitution; see `F33f`_`[Levenshtein distance`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Levenshtein_distance]`_`f for more information on these operations.

The implementation below performs `F33f`_`[fuzzy matching`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Probabilistic_record_linkage]`_`f (returning the first match with up to `*k`* errors) using the fuzzy bitap algorithm. However, it only pays attention to substitutions, not to insertions or deletions – in other words, a `F33f`_`[Hamming distance`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_distance]`_`f of `*k`*. As before, the semantics of 0 and 1 are reversed from their conventional meanings.

`B100`F9d9 #include <stdlib.h>`f`b
`B100`F9d9 #include <string.h>`f`b
`B100`F9d9 #include <limits.h>`f`b
`B100`F9d9`f`b
`B100`F9d9 const char *bitap_fuzzy_bitwise_search(const char *text, const char *pattern, int k)`f`b
`B100`F9d9 {`f`b
`B100`F9d9 const char *result = NULL;`f`b
`B100`F9d9 int m = strlen(pattern);`f`b
`B100`F9d9 unsigned long *R;`f`b
`B100`F9d9 unsigned long pattern_mask[CHAR_MAX+1];`f`b
`B100`F9d9 int i, d;`f`b
`B100`F9d9`f`b
`B100`F9d9 if (pattern[0] == '\\0') return text;`f`b
`B100`F9d9 if (m > 31) return "The pattern is too long!";`f`b
`B100`F9d9`f`b
`B100`F9d9 /* Initialize the bit array R */`f`b
`B100`F9d9 R = malloc((k+1) * sizeof *R);`f`b
`B100`F9d9 for (i=0; i <= k; ++i)`f`b
`B100`F9d9 R[i] = ~1;`f`b
`B100`F9d9`f`b
`B100`F9d9 /* Initialize the pattern bitmasks */`f`b
`B100`F9d9 for (i=0; i <= CHAR_MAX; ++i)`f`b
`B100`F9d9 pattern_mask[i] = ~0;`f`b
`B100`F9d9 for (i=0; i < m; ++i)`f`b
`B100`F9d9 pattern_mask[pattern[i]] &= ~(1UL << i);`f`b
`B100`F9d9`f`b
`B100`F9d9 for (i=0; text[i] != '\\0'; ++i) {`f`b
`B100`F9d9 /* Update the bit arrays */`f`b
`B100`F9d9 unsigned long old_Rd1 = R[0];`f`b
`B100`F9d9`f`b
`B100`F9d9 R[0] |= pattern_mask[text[i]];`f`b
`B100`F9d9 R[0] <<= 1;`f`b
`B100`F9d9`f`b
`B100`F9d9 for (d=1; d <= k; ++d) {`f`b
`B100`F9d9 unsigned long tmp = R[d];`f`b
`B100`F9d9 /* Substitution is all we care about */`f`b
`B100`F9d9 R[d] = (old_Rd1 & (R[d] | pattern_mask[text[i]])) << 1;`f`b
`B100`F9d9 old_Rd1 = tmp;`f`b
`B100`F9d9 }`f`b
`B100`F9d9`f`b
`B100`F9d9 if (0 == (R[k] & (1UL << m))) {`f`b
`B100`F9d9 result = (text+i - m) + 1;`f`b
`B100`F9d9 break;`f`b
`B100`F9d9 }`f`b
`B100`F9d9 }`f`b
`B100`F9d9`f`b
`B100`F9d9 free(R);`f`b
`B100`F9d9 return result;`f`b
`B100`F9d9 }`f`b

>>See also

• `F33f`_`[agrep`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Agrep]`_`f
• `F33f`_`[TRE (computing)`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=TRE_(computing)]`_`f

>>External links and references

1. `:endnote-domolki64`a`!`F33f`_`[^`#ref-domolki64]`_`f`! Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964.
2. `:endnote-domolki68`a`!`F33f`_`[^`#ref-domolki68]`_`f`! Bálint Dömölki, A universal compiler system based on production rules, `F33f`_`[BIT Numerical Mathematics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=BIT_Numerical_Mathematics]`_`f, 8(4), pp 262–275, 1968. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/BF01933436
3. `:endnote-shyamasundar77`a`!`F33f`_`[^`#ref-shyamasundar77]`_`f`! R. K. Shyamasundar, Precedence parsing using Dömölki's algorithm, `F33f`_`[International Journal of Computer Mathematics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=International_Journal_of_Computer_Mathematics]`_`f, 6(2)pp 105–114, 1977.
4. `:endnote-by89`a`!`F33f`_`[^`#ref-by89]`_`f`! Ricardo Baeza-Yates. "Efficient Text Searching." PhD Thesis, University of Waterloo, Canada, May 1989.
5. `:endnote-manber91`a`!`F33f`_`[^`#ref-manber91]`_`f`! Udi Manber, Sun Wu. "Fast text searching with errors." Technical Report TR-91-11. Department of Computer Science, `F33f`_`[University of Arizona`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=University_of_Arizona]`_`f, Tucson, June 1991. (gzipped PostScript)
6. `:endnote-byg92`a`!`F33f`_`[^`#ref-byg92]`_`f`! Ricardo Baeza-Yates, Gastón H. Gonnet. "A New Approach to Text Searching." `*`F33f`_`[Communications of the ACM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Communications_of_the_ACM]`_`f`*, 35(10): pp. 74–82, October 1992.
7. `:endnote-manber92`a`!`F33f`_`[^`#ref-manber92]`_`f`! Udi Manber, Sun Wu. "Fast text search allowing errors." `*`F33f`_`[Communications of the ACM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Communications_of_the_ACM]`_`f`*, 35(10): pp. 83–91, October 1992, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1145/135239.135244.
8. `:endnote-bn96`a`!`F33f`_`[^`#ref-bn96]`_`f`! R. Baeza-Yates and G. Navarro. A faster algorithm for approximate string matching. In Dan Hirchsberg and Gene Myers, editors, `*Combinatorial Pattern Matching`* (CPM'96), LNCS 1075, pages 1–23, Irvine, CA, June 1996.
9. `:endnote-m99`a`!`F33f`_`[^`#ref-m99]`_`f`! G. Myers. "A fast bit-vector algorithm for approximate string matching based on dynamic programming." `*`F33f`_`[Journal of the ACM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Journal_of_the_ACM]`_`f`* 46 (3), May 1999, 395–415.
10. libbitap, a free implementation that shows how the algorithm can easily be extended for most regular expressions. Unlike the code above, it places no limit on the pattern length.
11. Ricardo Baeza-Yates, Berthier Ribeiro-Neto. `*Modern Information Retrieval`*. 1999. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-201-39829-X.
12. bitap.py - Python implementation of Bitap algorithm with Wu-Manber modifications.

`c`F0af`_`[↑ Back to top`#top]`_`f`a